package leetcode.tree;

/**
 * @author wangmaolin1
 * @date 2022/1/3 下午7:08
 */
public class _543二叉树的直径 {

    int max = Integer.MIN_VALUE;

    /**
     * 做后序遍历，每次返回当前节点的最大深度
     * 后序遍历时，更新直径（直径可以理解为，某个树中，直径 m=max(任意节点的左右子树深度的和)
     */
    public int diameterOfBinaryTree(TreeNode root) {
        postOrder(root);
        return max;
    }


    private int postOrder(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = 0;
        int rightHeight = 0;
        if (root.left != null) {
            leftHeight = postOrder(root.left) + 1;
        }
        if (root.right != null) {
            rightHeight = postOrder(root.right) + 1;
        }
        int length = rightHeight + leftHeight;
        max = Math.max(length, max);
        return Math.max(leftHeight, rightHeight);

    }
    int res=0;
    public int diameterOfBinaryTree2(TreeNode root) {
        track(root);
        return res;
    }

    private int track(TreeNode root) {
        if (root ==null){
            return  0;
        }
        int maxLeft = track(root.left);
        int maxRight = track(root.right);
        res=Math.max(res,maxLeft+maxRight);
        return 1+Math.max(maxLeft,maxRight);
    }
}
